/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"

using namespace std;


/*void print_leaf(PageId pid, PageFile& pf)
{
    
    RC rc;
    BTLeafNode leaf;
    int eid=0;
    int key;
    RecordId rid;
    leaf.read(pid, (const PageFile)pf);
     fprintf(stderr, "leaf at (%d): %d\n\n", leaf.getKeyCount(),pid);
    while(eid< leaf.getKeyCount())
    {
        leaf.readEntry(eid, key, rid) ;
        eid++;
        fprintf(stderr, "%u ", key);
        
    }
    fprintf(stderr, "\n\n");

    
}
void print_non_leaf(PageId pid, PageFile& pf)
{
    
    RC rc;
    BTNonLeafNode nonleaf;
    int eid=0;
    int key;
    RecordId rid;
    nonleaf.read(pid, (const PageFile)pf);
    fprintf(stderr, "nonleaf at (%d): %d\n\n", nonleaf.getKeyCount(),pid);
    
    int entryNum=0;
    int numKey = nonleaf.getKeyCount();
    memcpy(&pid, nonleaf.buffer+sizeof(int), sizeof(PageId));
    fprintf(stderr, "(%u) ", pid);
    while(entryNum<numKey){
        //page id comes before key
        memcpy(&key, nonleaf.buffer+sizeof(int)+entryNum*NLEAF_ENTRY_SIZE+sizeof(PageId), sizeof(int));
        memcpy(&pid, nonleaf.buffer+sizeof(int)+(entryNum+1)*NLEAF_ENTRY_SIZE, sizeof(PageId));
        //if(debug) fprintf(stderr, "pid: %i, %u > %u (searchkey)\n", pid,key,searchKey);
        fprintf(stderr, "%u ", key);
        fprintf(stderr, "(%u)", pid);
        entryNum++;
    }
    fprintf(stderr, "\n\n");

    
}*/
/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    treeHeight=0;
    rootPid = -1;
    
}

BTreeIndex::~BTreeIndex()
{
    close();
}
/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
    writeable = false;
    if (mode == 'w' || mode == 'W') writeable = true;
    RC   rc;
    // open the page file in desired mode (to initialize if nonexistent)
    if ((rc = pf.open(indexname, mode)) != 0) return rc;
    
    //
    // in the rest of this function, we set pageid of root node and tree height
    //

    // If the file is empty(just got created), set rootPid to -1 and treeHeight to 0
    if (pf.endPid() <= 0){
        rootPid = -1;
        treeHeight = 0;
        char info[PageFile::PAGE_SIZE];
        //Initialize buffer for info page to zero
        memset(info, 0, (size_t)PageFile::PAGE_SIZE);
        
        //copy rootPid and treeHeight to the info page
        memcpy(info, &rootPid, sizeof(PageId));
        memcpy(info+sizeof(PageId), &treeHeight, sizeof(int));
    //else read the treeHieght and rootPid from the default info page (pid 0)
    }else{
        char info[PageFile::PAGE_SIZE];
            
        //open pagefile in read mode to initialize member variables
        //Read the first page (page with pid=0 is the info page) 
        if( pf.read(0, info) != 0) {
            return RC_FILE_READ_FAILED;
	}
        //first PageId(int type) value in page 0 is rootPid
        memcpy(&rootPid, info, sizeof(PageId));
        //second int value in page 0 is treeHeight
        memcpy(&treeHeight, info+sizeof(PageId), sizeof(int));
    }

    return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
        
    if(writeable){//If opened in write mode, treeHeight and rootPid may have changed. Write them to disk.
        char info[PageFile::PAGE_SIZE];
        
        //Initialize buffer for info page to zero
        memset(info, 0, (size_t)PageFile::PAGE_SIZE);
        
        //copy rootPid and treeHeight to the info page
        memcpy(info, &rootPid, sizeof(PageId));
        memcpy(info+sizeof(PageId), &treeHeight, sizeof(int));
        
        //write info page changes (to pid 0)
        if(pf.write(0,info)!=0){
            return RC_FILE_WRITE_FAILED; 
        }
    }
    
    pf.close();
    return 0;
}

/*
 * Recursivley insert (key, RecordId) pair to the index at tree depth 'depth'
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @param pid[IN] the node's page being read
 * @param depth[IN] the depth of the node being looked at
 * param overflow[OUT] if overflow, pass the overflowed 
 * @return 1 if overflow, 0 if not overflow, else error code
 */
RC BTreeIndex::runInsert(int key, const RecordId& rid, int pid, int depth, int& sibKey, int& sibPid)
{
   
    RC rc = -1;
    int oK;//hold overflow key?
    int oP;//hold overflow pid?

    if(depth<treeHeight)//If accessing a nonleaf node, insert into it
    {
        BTNonLeafNode nonleaf;
        //Find params for recursive call of this function & recursively call it
        if( ((rc = nonleaf.read(pid, pf)) < 0) ){ return rc;}
        int ChildPid;
        if( ((rc = nonleaf.locateChildPtr(key, ChildPid)) < 0) ){ return rc;}
        if(ChildPid == 0){
            fprintf(stderr, "Child pid ==0! key: %u for nonleaf pid: %u\n", key,pid);
        }
        if( ((rc = runInsert(key, rid, ChildPid, depth+1, oK,oP)) < 0) ){ return rc;}
        // If no overflow from call
        if(ChildPid ==0){
           fprintf(stderr, "Caller %u of %u\n", pid, ChildPid);
        }
        if(rc == 0)
        {
            return 0;
            
        }else if(rc == 1){// if overflow into this call's node
            //case: non leaf node overflows
            // fprintf(stderr, "Depth: %d, insert key from leave to: %d from childpid: %d\n", depth, pid, ChildPid);
            //fprintf(stderr, "Insert %u and %u, split non-leaf node %u\n",oK,oP,pid);
            if(nonleaf.getKeyCount() >= MAX_NLEAF_ENTRY)
            {
                sibPid = pf.endPid();
                BTNonLeafNode sib;
                
                //insert and split. get the midkey (that gets pushed up)
                if( ((rc =nonleaf.insertAndSplit(oK, oP, sib, sibKey)) < 0) ){ return rc;}
                
                //Save data to disk
                if( ((rc = nonleaf.write(pid,pf)) < 0) ){ return rc;}
                if( ((rc = sib.write(sibPid,pf)) < 0) ){ return rc;}
                //fprintf(stderr, "insert %u causes NONLEAF %u\n",oP, sibPid);
 
                //initialize new root node
                if(depth == 1){
                    rootPid = pf.endPid();
                    BTNonLeafNode root;
                    if( ((rc = root.initializeRoot(pid, sibKey, sibPid))< 0) ){ return rc;}
                    //Save data to disk
                    if( ((rc = root.write(rootPid,pf)) < 0) ){ return rc;}
                    //fprintf(stderr, "NONLEAF ROOT: %u with %u - %u - %u\n", rootPid, pid, sibKey, sibPid);
                    //increment tree height
                    treeHeight++;
                    //DEBUG
                    //fprintf(stderr, "New non-leaf root\n");
                    //print_non_leaf(rootPid, pf);
                    //print_non_leaf(pid, pf);
                    //print_non_leaf(sibPid, pf);
                    return 0;  
                    
                }
                return 1;
            }else{
                //else just insert the overflow to this call's node
                if( ((rc = nonleaf.insert(oK,oP)) < 0) ){ return rc;}
                if( ((rc = nonleaf.write(pid,pf)) < 0) ){ return rc;}
                //print_non_leaf(rootPid, pf);
                //print_non_leaf(rootPid, pf);
                return 0;
            }
        }
    //at the LEAF level, insert new leaf node
    }else{
        //read the leaf node information
        BTLeafNode leaf;
        if( ((rc = leaf.read(pid, pf)) < 0) ){ return rc;}
        
        //case: leaf node is full -> insert and split
        if(leaf.getKeyCount() >= MAX_LEAF_ENTRY){
            
            //initialize an empty sibling node
            BTLeafNode sib;
            sibPid = pf.endPid();
            
            //insert and split. Get the sibling key
            if( ((rc =leaf.insertAndSplit(key, rid, sib, sibKey)) < 0) ){ return rc;}
            if ( (rc = leaf.setNextNodePtr(sibPid)) <0) {return rc;}
            
            //Save current node and sibling node to disk
            if( ((rc = leaf.write(pid,pf)) < 0) ){ return rc;}
            if( ((rc = sib.write(sibPid,pf)) < 0) ){ return rc;}
            //fprintf(stderr, "New Split split!\n");
 
            //DEBUG
            /*fprintf(stderr, "The current leaf pid should be %d\n", pid);
            
            fprintf(stderr, "The sibling pid should be %d\n", sibPid);
            fprintf(stderr, "but it is actually %d\n", leaf.getNextNodePtr());
            */
            //Special case: if leaf is root, initialize new non-leaf root node
            if(treeHeight ==1){
                rootPid = pf.endPid();
                BTNonLeafNode root;
                if( ((rc = root.initializeRoot(pid, sibKey, sibPid))< 0) ){ return rc;}
                //Save data to disk
                if( ((rc = root.write(rootPid,pf)) < 0) ){ return rc;}
                //fprintf(stderr, "NONLEAF ROOT from leaves %u with %u | %u | %u\n", rootPid, pid, sibKey,sibPid);

                //increment tree height
                treeHeight++;
                
                //DEBUG
                //fprintf(stderr, "New non-leaf root from leaf root\n");
                return 0;
            }
            //fprintf(stderr, "Leaf %u overflows sibpid: %u and sibkey: %u\n", pid, sibPid,sibKey);

            
            return 1;
        }else{ 
            
            //case: leaf node is not full -> insert
            if( ((rc = leaf.insert(key,rid)) < 0) ){ return rc;}
            if( ((rc = leaf.write(pid,pf)) < 0) ){ return rc;}
            
            return 0;
        }
    }
    return rc;// Should not reach here
}
/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
    char info[PageFile::PAGE_SIZE];
    //special case: Index tree is empty -> initialize a leaf root node 
    if(rootPid == -1 || treeHeight==0){
        RC rc=-1;
        //insert key and rid
        BTLeafNode root;
        if( (rc = root.insert(key, rid))<0) { return rc; }
        
        rootPid = pf.endPid();

        if(rootPid == INFO_PAGE_PID)
        {
            rootPid++;
        }
        //Save data to disk
        //fprintf(stderr, "LEAF ROOT %u\n", rootPid);
        root.setNextNodePtr(RC_END_OF_TREE);
        if( ((rc = root.write(rootPid,pf)) < 0) ){ return rc;}
        treeHeight =1;
        //Save metadata to disk
        memset(info, 0, (size_t)PageFile::PAGE_SIZE);
        //copy rootPid and treeHeight to the info page
        memcpy(info, &rootPid, sizeof(PageId));
        memcpy(info+sizeof(PageId), &treeHeight, sizeof(int));
        //write info page changes (to pid 0)
        if(pf.write(0,info)!=0){
            return RC_FILE_WRITE_FAILED;
        }
        //fprintf(stderr, "Leaf root at id %u overflows and first key: %u\n", rootPid,key);
        return 0;    
    }else{
        int overFlowKey;
        int overFlowPid;
        //Save metadata to disk
        memset(info, 0, (size_t)PageFile::PAGE_SIZE);
        //copy rootPid and treeHeight to the info page
        memcpy(info, &rootPid, sizeof(PageId));
        memcpy(info+sizeof(PageId), &treeHeight, sizeof(int));
        //write info page changes (to pid 0)
        if(pf.write(0,info)!=0){
            return RC_FILE_WRITE_FAILED;
        }
        //fprintf(stderr,"Root: %d", rootPid);
        return runInsert(key, rid, rootPid, 1, overFlowKey, overFlowPid);//No overflow from call
    }
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
    
    //bool debug = false;
    //if(cursor.pid == -10)debug =true;
    //fprintf(stderr, "In locate\n");
    //Start at root node
    if(rootPid == -1 && treeHeight==0) return RC_EMPTY_TREE;
    //fprintf(stderr,"Root: %d", rootPid);
    
    BTNonLeafNode node;//Will hold target node's data
    RC rc; //will hold node function return codes
    int key;//will hold data to put in cursor
    RecordId rid;//will hold data to put in cursor
    int depth = 1; //track depth
    //Initialize to root:
    cursor.pid = rootPid;
    //fprintf(stderr,"ROOT: %u\n",cursor.pid);
    //Get through all nodes:
    //if treeHeight == 1 (root is the leaf node), then skip the step of traversing non-leaf nodes
        
    while(depth < treeHeight){//loop until all nonleaf levels traversed (i.e. end up at the leaf node)
        if (((rc = node.read(cursor.pid, (const PageFile)pf) ) < 0)) return rc;//Initialize node
        //if(debug)cursor.pid = -10;
        if (((rc = node.locateChildPtr(searchKey, cursor.pid)) < 0)) return rc;//Move cursor to correct entry in node
        node.read(cursor.pid,pf);
        //if(debug)fprintf(stderr,"@depth: %u/%u, pid goes to %u,(%u possible)", depth,treeHeight, cursor.pid, node.getKeyCount());
        depth++;
    }
    //loop through data of the leaf node (exit when key found with eid, pid already set)
    BTLeafNode leaf;
    if (((rc = leaf.read(cursor.pid, (const PageFile)pf) ) < 0)) return rc;//Initialize leaf node
    //fprintf(stderr, "READING: page %u (%u == %u)\n", cursor.pid, depth, treeHeight);
    if (((rc = leaf.locate(searchKey, cursor.eid)) < 0)) return rc;//Move cursor to correct entry in leaf
    
    //return the position of the
    return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
    RC rc;
    BTLeafNode leaf;
    
    if (((rc = leaf.read(cursor.pid, (const PageFile)pf) ) < 0)) return rc;//Initialize leaf node
    if (((rc = leaf.readEntry(cursor.eid, key, rid) ) < 0)) return rc;//read leaf node
 
    cursor.eid++;

    
    //if eid is the biggest eid, move to the next sibling node
    if(cursor.eid == leaf.getKeyCount())
    {
       if( (rc=leaf.getNextNodePtr())<=0) return rc;
        cursor.pid = leaf.getNextNodePtr();
        cursor.eid = 0;
    }
    return 0;
}
